The Past
There is an important difference between analog and digital circuits, especially when the circuits are used for complex computations and other complex processing. Analog circuits are primarily subject to the laws of physics, while digital circuits must obey the rules of logic. This has numerous implications.
At one time, all electrical devices, such telephones, radios, televisions used analog circuits. Even the first computers were analog. Generally, analog circuits are faster, less complex, use less power, and are smaller in size than equivalent digital circuits to perform similar processing tasks. But, perhaps most important, analog circuits can operate on analog values and analog states that represent, for example, real or complex numbers.
However, analog circuits have a major disadvantage when compared with digital circuits. Analog circuits are more prone to errors than, digital circuits. This is because analog circuits are relatively susceptible to noise, uncontrollable variations in fabrication processes, systematic or non-systematic faults, parasitic effects, defects, component mismatch, offsets, non-linearities, and sometimes hard to control environmental conditions. This makes it difficult to use analog circuits in the mass production of large complex systems, as demanded for modern electronic devices.
Consequently, digital circuits are now ubiquitous, filling an insatiable consumer market. Computers came first, later followed by digital telephones, television and radio, and innumerable other electronic digital devices. However, digital circuits also have disadvantages. When compared with analog circuits, digital circuits are relatively slow. But more important, digital circuits can only operate on discrete values, for example, 0 and 1. This requires that the input signals need first to sampled and quantized. Switching between permissible discrete states in digital circuits also takes more time than smoothly slewing analog states that have close together values in an analog circuit,
The Present
Herein, error correction and error reduction are distinguished. Error correcting codes and error correcting decoders work together to form a system for removing errors from data that has been corrupted by being sent across a noisy channel. The existence of error correcting codes was described by Claude Shannon in 1958 when he proved his well known channel capacity theorem. The first examples of error correcting codes were described by Hamming in 1960, Recently the field of coding was revolutionized when turbo codes and then low-density parity check (LDPC) codes were shown to both achieve very close to the Shannon channel capacity and to be decodable by relatively low-complexity error correction decoding algorithms. So called soft decoders are in fact these low-complexity error-correction decoders for turbo codes and LDPC codes. Soft decoders have been implemented with analog circuits, and have been shown to correct noise introduced by a noisy channel. For this to be possible, however, the data sent through the channel must first be encoded using an error correcting code. Those analog error correction decoders do not correct noise introduced by the circuit itself, they only correct errors due to channel noise. Error reduction is distinguished below.
Errors in Analog Circuits
Hans-Andreas Loeliger states that, “It is commonplace that analog circuits are sensitive to noise, temperature, and component variations, and are therefore hard to design and expensive to manufacture.” Hans-Andreas Loeliger, “Analog decoding and beyond,” Information Theory Workshop, 2001. Proceedings, ISBN: 0-7803-7119-4, 2001 IEEE, pp. 126-127, September 2001. He goes on to state that, “it has always been known that analog computation is sometimes much faster or less power consuming than digital computation,” and that “indeed, Carver Mead has demonstrated unconventional adaptive analog systems for a number of signal processing tasks (primarily in image processing) that share the robustness of digital systems but use several orders of magnitude less power,” and finally that “the most interesting modes of analog computation, may yet remain to be discovered.”
Analog Fast-Fourier Transform
Donald A. Gaubatz, in “FFT-Based Analog Beam-forming Processor” Ultrasonics Symposium Proceedings, pages 676-681, 1976, describes an example of processing with analog circuits. Gaubatz states that, “Analog signal processing requires stringent design constraints to assure accuracy and repeatability, but the resulting speed and relative economy are compensating factors.” Although Gaubatz describes a method for implementing a fast Fourier transform (FFT) with analog circuits, “the stringent design constraints” he employs to “assure accuracy” is to tediously selected discrete devices, each on its own die and in its own package, and to test each device to assure that the device matches the other devices before using the device in the FFT. Clearly, that technique is not amenable to mass production.
Transistor mismatch can be due to transistors being manufactured either too large or too small in either width or length, by variations in the distribution of dopant atoms from transistor to transistor, by variations in oxide thickness, or by other causes. Gaubatz proposes to use discrete transistors so that each, transistor can be tested individually. He discards individual devices that do not match one another sufficiently. However, analog circuits manually constructed from a large set of individual discrete components are not cost competitive with modern, very-large-scale digital integrated circuits.
It would be impossible to implement Gaubatz's analog FFT circuit in modern integrated circuits, because an integrated version, would not be able to employ his tedious method of only using matching devices, and discarding mismatched devices.
In successive generations of integrated circuits, as transistors have been manufactured in smaller and smaller sizes, the effect of mismatch has increased because improvements in manufacturing tolerances have not kept up with deceased device scaling. For this reason, engineers designing integrated circuits often select to use integrated devices that are much larger than a minimum feature size of the process to avoid the worst effects of mismatch. This increases cost and power, and makes the circuits slower. The end result is that analog circuits do not benefit from Moore's law scaling,
Analog designers can also use other methods to reduce mismatch errors. For example U.S. Pat. No. 4,386,155, “High-accuracy four-quadrant multiplier which also is capable of four-quadrant division” issued to Gilbert on Apr. 29, 1986, describes a four-quadrant analog multiplier. Gilbert describes a method for reducing errors introduced by temperature fluctuations in the circuit wherein “resistors are connected . . . and current which is proportional-to-absolute-temperature is caused to flow through the resistors. There, the resistors are laser-trimmed until VBE mismatch distortion is nulled.” That method requires a separate circuit to measure the amount of mismatch or error due to temperature fluctuation, and to compensate by supplying additional current. Furthermore, in that method, resistors must be matched by laser trimming. Such methods are not suited for mass production, or very large scale integrated systems.
The Gaubatz method for assuring repeatability, in the presence of noise, is again to use large discrete devices operating at relatively large voltages, so that the average noise voltage in the circuit is small with respect to the overall voltage swing of the devices. As semiconductor fabrication processes improve and the size of transistors decreases, the supply voltage VDD also decreases. This means that the available voltage swing of devices decreases. However, the average noise-power does not decrease significantly. If a very small, low-power, integrated version of Gaubatz's circuits were manufactured in the attempt to be competitive against the power and area consumption of a digital circuit, the noise would be extremely disruptive to the processing because the average noise voltage would be equal to a significant percentage of the total voltage swing in the circuits.
U.S. Pat. No. 5,495,554, “Analog Wavelet Transform Circuitry,” issued to R. Timothy Edwards and Michael D on Feb. 27, 1996, describes “an analog circuit implementing a continuous wavelet transform.” That analog circuit is estimated to be about one-hundredth ( 1/100) the size and power of a digital wavelet transform circuit. Edwards et al. state that “the analog wavelet outputs of the analog wavelet transform chip is directly determined without the loss of information due to the digital sampling.” They do not describe a method for reducing the effects of errors introduced in their analog processing.
U.S. Pat. No. 6,954,423, “Analog Implementation of Linear Transforms,” issued to Frank A. Tinker on Oct. 11, 2005, describes a system that performs “a linear transformation of a data set of discrete values . . . provided as a set of analog signals to the input nodes.” The transform “is achieved by judiciously adjusting the signal amplitude produced at the output of the phase-shift components and summing the resulting output signals as required to simulate the transformation of interest.” They do not describe a method for reducing the effects of errors introduced in their analog processing.
The processes that can be used with the embodiments of the invention can include linear transforms, linearized transforms, unitary transforms, statistical inferences, normalized belief propagations, solving linear differential equations, solving linearized differential equations, matrix inverses, minimizing functions, or other functions that obey any conservation or scaling law.
Analog Processing of Error Correction Decoding for Communications
Like the FFT, error-correction decoding is an important and computationally intensive processing task performed by communication transceivers. Analog circuits for decoding error-correcting codes are known. In contrast to analog Viterbi decoders, the decoders are based on turbo codes described by factor graphs.
U.S. Pat. No. 7,071,846 “Analog Decoding Method and Decoder” issued to Moerz on Jul. 4, 2006, describes “an analog decoder,” Moerz applies to parallelization of decoding of convolutional turbo codes. Error reduction is not described.
U.S. Pat. No. 6,282,559 “Method and electronic circuit for signal processing, in particular for the computation of probability distributions” issued to Helfenstein et al. on Aug. 28, 2001, describes a circuit module wherein “the currents of the outputs correspond to the product of the currents through the individual inputs. By combining the outputs, sum products can be calculated, especially for processing discrete probability distributions. The combination of several circuit modules allows to solve complex signal processing tasks.” They do not describe a method for reducing the effects of errors introduced in their analog processing. The error correction decoder they describe only corrects the effects of errors introduced in the communication channel before the noisy signal enters the error correction decoder system. Noise and other errors introduced by the decoder itself are not addressed.
Although the circuits according to Loeliger et al. can perform error correction decoding of data received over a noisy channel, their circuits still suffer from internal errors introduced while the processing, see Felix Lustenberger and Hans-Andrea Loeliger, “On Mismatch Errors In Analog-VLSI Error Correcting Decoders,” Proceedings of ISCAS, May 2001, They analyze their “new type of nonlinear analog transistor networks . . . proposed for ‘turbo’ decoding of error correcting codes.” They state that, “the influence of various non-idealities on the performance of such analog decoders is not yet well understood.” They describe “the performance degradation due to transistor mismatch.” They “assume . . . that each transistor in the circuit is affected by transistor mismatch,” and they “compare the accuracy of analog decoders with that of digital decoders,” Again, Loeliger et al. only analyze the effect of mismatch, in the operation of the decoder circuit. They do not describe any method or apparatus to remedy the effects of mismatch in their circuits.
Loeliger et al. only analyze how to derive output-referred errors due to transistor mismatch in analog translinear circuits. Their circuits are capable of processing two probability distributions as inputs to produce a third probability distribution as an output. All inputs and outputs are discrete probability distributions, such as are commonly found in a histogram. In a probability distribution for a discrete stochastic variable, each possible discrete state of the variable is assigned a probability such that a sum of the probabilities that the variable is in any of its possible states is 100%. They represent the “analog” probability of a given discrete state of a variable as an analog current on a wire. Each discrete state that a variable may occupy is signaled on an associated wire. For example, for a binary variable that can be either zero or one, they use two wires where one wire signals the probability that the variable is a one, and the other wire signals the probability that the variable is a zero. Because that system uses wires carrying analog values, and devices that directly process these analog values, it is an analog circuit operating on discrete variables and states (0 or 1).
FIG. 2 is a schematic diagram of their circuit. In FIG. 2, inputs 200-201 are currents representing probability values of discrete state of a stochastic variables. Output currents are 202-205. Their circuit uses a voltage reference 206 that sets the DC offset for the corresponding input 211. Another voltage reference 207 sets the DC offset for the corresponding input 210. The circuit also includes sub-threshold-mode-MOSFETs 208-211, Transistor 209 takes the logarithm of the input current and produce a voltage that controls the gate of transistor 210. Transistor 208 takes the logarithm of the input current and produce a voltage that controls the gate of transistor 211. They only describe analog circuits using either subthreshold-mode-MOSFETs or BJTs. In fact, the circuit of FIG. 2 cannot perform the function they describe using any other kind of transistor.
They only describe circuits with exponential-components stating that, “the transistors will be modeled as exponentially behaving voltage controlled current sources.” As described above, the use of exponential-components requires that the circuit be composed of either a set of MOSFETs operating in the below-threshold mode, or BJTs.
There are problems with those restrictions because MOSFETs operating in the below-threshold mode have the disadvantage of being very slow. Generally, MOSFETS cannot operate faster than a few hundred kHz, and usually only operate in the tens of kHz range. MOSFETs certainly cannot attain the more than GHz speeds achieved by above-threshold MOSFET devices employed in conventional digital processors. To make up for the slow speed, one can sometimes use more MOSFETs to operate in parallel. However, then leakage currents become an additional cause for errors, and the circuit size increases.
BJTs require a more complicated and more expensive manufacturing process than MOSFETs. Generally, BJT require quite a large amount of power and are also bigger than MOSFETs. Thus, BJTs require more semiconductor area. Primarily because of their much greater cost and manufacturing difficulty, BJTs are used infrequently in large-scale applications.
Errors in Digital Circuits
As stated above, digital circuits operate exclusively on discrete values and discrete states. Most often, 0 and 1. This makes it relatively easy to detect and correct errors, when compared with analog circuits. There are two basic methods for correcting errors introduced in digital circuits by any cause.
The first method is to use only discrete or “digital” states to represent information in the processing. In a binary digital circuit, a state must be a either zero or one in order to be considered a valid state. Comparators or comparator-like components in digital circuits force any state that is found to be in between zero and one to be made into a zero or one.
For example, if in a digital circuit ground GND=0, and a supply voltage VDD=1V, then a state=0.6V cannot propagate through the circuit. Because the state is greater than 0.5V, the state is forced to VDD by the digital circuits, or failing this, the state may simply be considered invalid and the entire computation can fail. Errors in a digital, circuit cannot cause states to be greater than one, because a one is the same as VDD and a state cannot achieve a voltage greater than VDD. Similarly, a state cannot achieve a voltage less than GND, so states cannot be less than zero. In this way, each individual bit in a digital computing circuit is always forced to be either VDD or GND, i.e., 1 or 0 respectively.
The second method for error correction, in digital processing due to noise deviations is to use error-correcting codes (ECC).
That method has always required the use of digital states. When using digital (binary) states or bits, the system can then make a copy of these bits or add parity check bits. Then, at some later time, the system can take advantage of the extra parity bits to detect and even correct errors that have been introduced.
Again, consider the digital circuit, which uses GND=0V and VDD=1V. Strong noise, mismatch, or other kinds of defects can invert a zero state to a one state, or vice versa. For example, a state that should be at GND could end up at 0.6V because of noise. Then, the digital circuit forces the state to VDD because the state is greater than 0.5V. If bits are inverted in a computation, this can result in wrong answers or even in the digital computer failing to complete its task.
Error correcting codes have been used to successfully correct errors due to noise in channels. When using error-correcting codes, redundant bits are sent. That decreases throughput. This slow-down due to the redundant bits results in a lower channel capacity, a maximum, rate at which information can be sent across the channel.
Methods have been described for treating noise that affects bits in computing circuitry as if the noise were noise on the actual bits traversing the channel. In contrast to noisy channels, noise in digital computing circuits has somewhat worse consequences. Not only does the need to error correct in digital circuits result in a similar slowdown in the rate of useful computation, but it also requires extra circuitry to implement the error-correction functionality.
For example, as shown in FIG. 3, the noise in a digital (Boolean) circuit is so bad that the result from a single Boolean logic circuit 300 cannot be trusted as being correct. One could add second and third copies 301-302 of this same circuit 300 and take a vote of the results from the three circuits. If two circuits agreed in their result, then that would be the answer used. An error-correction decoder circuit 303 essentially takes a vote of the results from the three circuits Boolean circuits 300-302. If the results from two of the circuits agreed, that result is used as the final output. In any case, error correction by any conventional means requires additional logic circuits and processing. This increases cost and processing time.
More complex techniques use recursive redundancy, block codes, or Reed-Solomon codes, or other kinds of more sophisticated codes. All of those techniques are essentially nothing more than complicated ways to structure redundant logic, and eventually “count votes.” The additional overhead for applying error-correction codes to digital computing circuits has meant that those techniques tend only to be used in mission critical circuits, where the additional expenditure of area and power is necessary.
U.S. Pat. No. 7,006,267 “Techniques for high fidelity quantum teleportation and computing” issued to Franson, et al. on Feb. 28, 2006 describes a method for using ancilla photons to assure high fidelity quantum teleportation. Ancilla photons are used to provide extra discrete states that function analogous to that of parity bits in error-correction codes. The additional states carry redundant information so that errors can be corrected,
Quantum error correction is known in the art, see for example, Seth Lloyd and Jean-Jacques Slotine, “Analog Quantum Error Correction,” Physical Review Letters 80, 4088-4091, Issue 18, May 1998, They describe an idea for error correction on analog variables, but only for quantum-mechanical analog variables, that are quantum entangled. The mathematics of quantum mechanics are quite different from that of classical physical systems. The idea for quantum analog error correction described requires quantum entanglement and quantum measurement to be available in order to be implemented. They state clearly that their idea may only be a theoretical curiosity and they do not propose a practical system for implementing the idea. Furthermore their idea requires quantum an cilia bits, which are essentially discrete parity bits for a quantum system.
U.S. Pat. No. 7,131,054, “Apparatus and method for efficient decoder normalization” issued to Greenberg et al. on Oct. 31, 2006 describes an apparatus and method “for normalizing a set of state metric values stored in a set of accumulators,” They describe a method for performing normalization comprising: if a specified normalization condition is met, subtracting a normalization amount from a branch metric value. That system uses an “accumulator in each . . . unit [which] has a fixed precision. Therefore, all accumulators are normalized periodically to prevent overflow. They describe a method for performing normalization only when a “specified normalization condition is met.” The normalization condition occurs when the accumulators are close to overflow.
Avoiding overflow is a completely different goal than reducing errors. The use of the term normalization is misleading, because they use normalization to mean reducing the magnitude of a variable.
When processing according to probability distributions, it is frequently necessary to perform normalization in order to assure that intermediate or final probability distributions are obey the rules for a properly defined probability distribution, namely that the total chance that all possible events occur cannot exceed 100%. This normalization is necessary even if the system has perfectly error-free computing hardware.
The Future
It is desired to provide an analog circuit that is a substantially error free.